package binarytree;

/**
 * Diameter0fBinaryTree 二叉树的直径
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: leetcode:https://leetcode-cn.com/problems/diameter-of-binary-tree/
 * @date 2021/5/7
 **/
public class Diameter0fBinaryTree {

    class Solution1 {

        int ans;

        public int diameterOfBinaryTree(TreeNode root) {
            ans = 1;
            depth(root);
            return ans - 1;
        }

        public int depth(TreeNode node) {
            if (node == null) return 0; // 访问到空节点了，返回0
            int leftDepth = depth(node.left); // 左儿子为根的子树的深度
            int rightDepth = depth(node.right); // 右儿子为根的子树的深度
            ans = Math.max(ans, leftDepth + rightDepth + 1); // 计算d_node即L+rightDepth+1 并更新ans
            return Math.max(leftDepth, rightDepth) + 1; // 返回该节点为根的子树的深度
        }
    }

    class Solution2 {

        public int diameterOfBinaryTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftDepth = findMaxDepthFromRoot(root.left, 1);

            int rightDepth = findMaxDepthFromRoot(root.right, 1);

            return leftDepth + rightDepth - 2;
        }

        private int findMaxDepthFromRoot(TreeNode node, int cur) {
            if (node == null) return cur;

            int l = findMaxDepthFromRoot(node.left, cur + 1);

            int r = findMaxDepthFromRoot(node.right, cur + 1);

            return Math.max(l, r);
        }
    }
}
